// 
// thinning
// thinning.cpp
// 
// The MIT License
// 
// Copyright (c) 2009 sonson, sonson@Picture&Software
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//#include "imgtool.h"	#define D2F(d) (int)((d) * 65536)#define F2I(f) ((f) >> 16)#define ABS(a) ((a) < 0 ? -(a) : (a))#define THRESHOLD 100#define DUMMY_MINUS_ONE	128	//// general image processing//unsigned char* binarize ( unsigned char* input, int width, int height ) {	unsigned char* output;	output = ( unsigned char* ) malloc ( sizeof ( unsigned char ) * width * height );	if ( !output )		return NULL;	for ( int x = 0; x < width; x++ ) {		for ( int y = 0; y < height; y++ ) {			int r = *( input + 3 * ( width * y + x )     );			int g = *( input + 3 * ( width * y + x ) + 1 );			int b = *( input + 3 * ( width * y + x ) + 2 );			int iy =  F2I(D2F(0.299) * r + D2F(0.587) * g + D2F(0.114) * b);			if ( iy > THRESHOLD )				*( output + width * y + x ) = 0;			else				*( output + width * y + x ) = 1;		}	}	return output;}void gain ( unsigned char* input, int width, int height ) {	for ( int x = 0; x < width; x++ )		for ( int y = 0; y < height; y++ )			*( input + width * y + x ) *= 255;}//// image process functions for thinning//int calc4connected ( int*f ) {	int n = 0;	for( int i = 0; i < 4; i++ ) {		int k = 2*i + 1;		n += ( f[k] - f[k] * f[k+1] * f[k+2] );	}	return n;}int calc8connected ( int*f ) {	int n = 0;	for( int i = 0; i < 4; i++ ) {		int k = 2*i + 1;		n += ( !f[k] - !f[k] * !f[k+1] * !f[k+2] );	}	return n;}//// for Hilditch Thinning//// for calculating the 6th condition of Hilditchint hilditchCondition6 ( int *f ) {	for ( int i = 1; i < 9; i++ ) {		if ( f[i] == -1 ) {			int tmp = f[i];			f[i] = 0;			int connect8  = calc8connected( f );			f[i] = tmp;			if ( connect8 != 1 ) {				f[i] = tmp;				return false;			}		}	}	return true;}	unsigned char hilditchConditions ( unsigned char* pixel, int width, int height, int x, int y ) {	int f[10];	f[4] = *( pixel + ( y - 1 ) * width + ( x - 1 ) );	f[3] = *( pixel + ( y - 1 ) * width + ( x     ) );	f[2] = *( pixel + ( y - 1 ) * width + ( x + 1 ) );	f[5] = *( pixel + ( y     ) * width + ( x - 1 ) );	f[0] = *( pixel + ( y     ) * width + ( x     ) );	f[1] = *( pixel + ( y     ) * width + ( x + 1 ) );	f[6] = *( pixel + ( y + 1 ) * width + ( x - 1 ) );	f[7] = *( pixel + ( y + 1 ) * width + ( x     ) );	f[8] = *( pixel + ( y + 1 ) * width + ( x + 1 ) );	f[9] = f[1];	// replace -1 <-> DUMMY_MINUS_ONE value	for ( int i = 0; i < 10; i++ )		if ( f[i] == DUMMY_MINUS_ONE )			f[i] = -1;	// condition1	if ( f[0] == 0 )		return false;	// condition2	int b = 0;	for ( int i = 0; i < 4; i++ ) {		int k = 2*i + 1;		b += ( 1 - abs( f[k] ) );	}	if ( !( b >= 1 ) )		return false;	// condition3	int e = 0;	for ( int i = 1; i < 9; i++ )		e += abs( f[i] );	if ( !( e >= 2 ) )		return false;	// condition4	int iso = 0;	for ( int i = 1; i < 9; i++ )		if ( f[i] == 1 )			iso++;	if ( !( iso >= 1 ) )		return false;	// condition5	if ( calc8connected ( f ) != 1 )		return false;	// condition6	if ( !hilditchCondition6 ( f ) )		return false;	return true;}	int hilditchThinning ( unsigned char* pixel, int width, int height ) {	int counter = 0;	// thinning	for ( int y = 1; y < height - 1; y++ ) {		for ( int x = 1; x < width - 1; x++ ) {			if ( hilditchConditions ( pixel, width, height, x, y ) ) {				*( pixel + width * y + x ) = DUMMY_MINUS_ONE;				counter++;			}		}	}	// replace -1 into 0	for ( int y = 0; y < height; y++ )		for ( int x = 0; x < width; x++ )			*( pixel + width * y + x ) = *( pixel + width * y + x ) == DUMMY_MINUS_ONE ? 0 : *( pixel + width * y + x );	return counter;}	int main ( int argc, char **argv ) {	int width, height;	unsigned char*pixel = NULL;		if ( argc != 2 )		return 0;	pixel = magick_read ( *(++argv), &width, &height, "RGB" );	if ( !pixel )		return 0;		// show before	showRGBPixelsInWindow ( pixel, width, height );	// binarize 0 or 1	unsigned char *bin = binarize ( pixel, width, height );	free ( pixel );	// thinning the binary image.	while( 1 ) {		if( !hilditchThinning ( bin, width, height ) )			break;	}	// show after and amplicated pixel's values	gain( bin, width, height );	showGrayPixelsInWindow ( bin, width, height );	free ( bin );	return 0;}